//输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 
//
// 
//
// 参考以下这颗二叉搜索树： 
//
//      5
//    / \
//   2   6
//  / \
// 1   3 
//
// 示例 1： 
//
// 输入: [1,6,3,2,5]
//输出: false 
//
// 示例 2： 
//
// 输入: [1,3,2,6,5]
//输出: true 
//
// 
//
// 提示： 
//
// 
// 数组长度 <= 1000 
// 
// Related Topics 栈 树 二叉搜索树 递归 二叉树 单调栈 👍 525 👎 0


package leetcode.editor.cn;

//Java：二叉搜索树的后序遍历序列
public class ErChaSouSuoShuDeHouXuBianLiXuLieLcof {
    public static void main(String[] args) {
        Solution solution = new ErChaSouSuoShuDeHouXuBianLiXuLieLcof().new Solution();
        // TO TEST
        System.out.println(solution.verifyPostorder(new int[]{1, 6, 3, 2, 5}));
        System.out.println(solution.verifyPostorder(new int[]{1, 3, 2, 6, 5}));
        System.out.println(solution.verifyPostorder(new int[]{5, 7, 6, 9, 11, 10, 8}));
        System.out.println(solution.verifyPostorder(new int[]{7, 4, 6, 5}));
        System.out.println(solution.verifyPostorder(new int[]{1}));
        System.out.println(solution.verifyPostorder(new int[]{2, 1}));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 判断：是否是二叉搜索树的后序遍历结果
         * 后序遍历：左右根
         * 左节点 < 根节点 < 右节点
         * 左节点 < 右节点, 根节点 < 右节点, 左节点 < 根节点
         * 后序遍历，最后一个节点一定是根节点，[左，右，根]
         *
         * @param postorder
         * @return
         */
        public boolean verifyPostorder(int[] postorder) {
            // [1,6,3,2,5]
            // [1,3,2,6,5]
            return verifyPostorderSub(postorder, 0, postorder.length);
        }

        /**
         * 判断子树是否是：二叉搜索树的后序遍历结果
         *
         * @param postorder
         * @param start
         * @param end
         * @return
         */
        public boolean verifyPostorderSub(int[] postorder, int start, int end) {
            if (end - start <= 1)
                return true;
            boolean result = true;
            int root = postorder[end - 1];
            // 把左子树，右子树，拆分开
            int leftStart = start, leftEnd = start;
            while (leftEnd < end) {
                if (postorder[leftEnd] < root) {
                    leftEnd++;
                } else {
                    break;
                }
            }

            int rightLeft = leftEnd, rightEnd = leftEnd;
            while (rightEnd < end) {
                if (postorder[rightEnd] > root) {
                    rightEnd++;
                } else {
                    break;
                }
            }
            result = (end - start) == (leftEnd - leftStart + rightEnd - rightLeft + 1);
            return result && verifyPostorderSub(postorder, leftStart, leftEnd) && verifyPostorderSub(postorder, rightLeft, rightEnd);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
